The technical field of this invention is signal processing and, in particular, the estimation of motion in motion picture frames.
A motion picture is composed of a sequence of still frames which are displayed in rapid succession. The frame rate necessary to achieve proper motion rendition in typical visual scenes is sufficiently high that there is a great deal of temporal redundancy among adjacent frames. Most of the variation from one frame to the next is due to object motion. This motion may occur within the scene or relative to the camera which generates the sequence of still frames.
There are a wide variety of applications where one desires to manipulate a motion picture by exploiting the temporal redundancy. In order to do this, it is necessary to account for the presence of motion. A number of systems are known for determining the movement of objects within the sequence of still frames. The process of determining the movement of objects within image sequences is known as motion estimation.
In general, prior systems for motion estimation have encountered three primary problems. First, such systems often have difficulty in accurately estimating motion in noisy images. Many systems are explicitly formulated under the assumptions of high signal-to-noise level. As a consequence, if the systems are applied to noisy pictures, the motion estimation errors are typically large. Most motion-compensated, image-processing systems require very accurate motion estimates in order to maintain adequate picture quality.
Second, objects within the image sequence which move with large velocities are difficult to track. In real-life motion pictures, the velocity field is a complicated function of spatio-temporal position; different parts of a motion picture move with different velocities. Therefore, most motion estimation systems are based on local operations (i.e., motion is estimated over a small region of the image). One of the problems with this approach is that typically only small velocity fields can be estimated reliably.
Third, the need to reduce computational complexity is an ever-present problem. Many applications of motion compensation require real-time operation. For real-time operation to be feasible, it is necessary for the system to be computationally efficient. Even in those applications where real-time operation is not required, computational complexity is an important characteristic which affects the cost of implementing a specific motion estimation system.
There exists a need for better motion estimation systems. Systems that address the problems of background noise, large velocities and computational complexity would satisfy a long-felt need in the art. It is an object of the present invention to provide better motion estimation systems for image processing purposes, including speed alteration, still image enhancement, picture coding and various other applications.
In the description of the present invention, matrix and vector notations are used. Matrices are represented with upper case symbols (A, B, etc.) and vectors are represented with either upper or lower case symbols with a bar over the symbol (a, b, S etc.). For example, a set of linear equations is written as EQU Ax=b.
The inverse of a matrix A is written as A.sup.-1, and the transpose is written as A.sup.T. Entries to a matrix are referred to with indexed notation. Therefore, A.sub.ij or A(i,j) refers to the i.sup.th row and j.sup.th column of matrix A.
All vectors are column vectors. Entries of a vector are referred to with subscripted notation. Therefore, b.sub.i refers to the i.sup.th element of vector b.
The signals are either single images or sequences of images which comprise a motion picture. The luminance of an image is a function of two variables, x and y. For the sake of notational convenience, the tuple (x,y) will be written as x in many occasions. Therefore, the image s(x,y) is equivalent to the image s(x). Continuous sequences of images are written as s(x,y,t)=s(x,t). Therefore, s(x,t.sub.o) refers to the frame at the time instant t.sub.o.